/*
673. 最长递增子序列的个数
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
medium, 彭珵 2024.9.13
*/

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 创建一个二维动态规划数组，大小为 (word1.size() + 1) x (word2.size() + 1)
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));

        // 初始化第一列，表示将 word1 转换为空字符串所需的删除操作数
        for (int i = 0; i <= word1.size(); i++) {
            dp[i][0] = i; // 删除所有字符
        }

        // 初始化第一行，表示将空字符串转换为 word2 所需的插入操作数
        for (int j = 0; j <= word2.size(); j++) {
            dp[0][j] = j; // 插入所有字符
        }

        // 填充动态规划表
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 如果当前字符相同，则不需要额外操作
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]; // 继承左上角的值
                } else {
                    // 计算插入和删除的最小操作数
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }

        // 返回将 word1 转换为 word2 的最小操作数
        return dp[word1.size()][word2.size()];
    }
};